﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Digraphs;

namespace Algoritmia.Problems.Closures
{
    public class DigraphTransitiveClosureFinder<T> : IDigraphTransitiveClosureFinder<T>
        where T : IEquatable<T>
    {
        private readonly Func<IDigraph<T>, IMatrixTransitiveClosureFinder> _createMatrixTransitiveClosureFinder;
        private readonly Func<IEnumerable<T>,IEnumerable<Tuple<T,T>>, IDigraph<T>> _createDigraph;

        public DigraphTransitiveClosureFinder(Func<IDigraph<T>,IMatrixTransitiveClosureFinder> createMatrixTransitiveClosureFinder = null,
            Func<IEnumerable<T>,IEnumerable<Tuple<T,T>>,IDigraph<T>> createDigraph = null)
        {
            _createMatrixTransitiveClosureFinder = createMatrixTransitiveClosureFinder ?? 
                (g => new WarshallMatrixTransitiveClosureFinder());
            _createDigraph = createDigraph ?? ((v, e) => new Digraph<T>(v, e));

        }

        public IDigraph<T> TransitiveClosure(IDigraph<T> g)
        {
            var vertices = g.V.ToArray();
            var n = vertices.Length;

            var result = _createMatrixTransitiveClosureFinder(g).TransitiveClosure((from i in Enumerable.Range(0, n)
                                                                                    select
                                                                                        (from j in Enumerable.Range(0, n)
                                                                                         select
                                                                                             g.E.Contains(
                                                                                                 new Tuple<T, T>(
                                                                                                     vertices[i],
                                                                                                     vertices[j]))).
                                                                                        ToArray()).ToArray());
            return
                _createDigraph(vertices, 
                    from i in Enumerable.Range(0,vertices.Length)
                    from j in Enumerable.Range(0, vertices.Length)
                    where result[i][j]
                    select new Tuple<T, T>(vertices[i], vertices[j]));
        }
    }
}
